LeetCode Longest Increasing Subsequence 题解

发表于   |  

LeetCode Longest Increasing Subsequence 题解。

原题

大意就是在一个未排序的数组中找出最长递增子序列的长度。

Constraints

  1. 未排序的int数组
  2. 数组长度未说明，可能为0
  3. 递增子序列：子序列就是从原数组中去除掉任意个元素（任意位置）所剩下的元素组成的序列（也就是说子序列中元素原先不必是相邻的），递增表示子序列后面的数比前面的大
  4. 返回最长子序列的长度，如果数组为0就返回0

Ideas

第一个想法

先创建一个数组dp，dp[i]表示以数组中第i个元素结尾的最长递增子序列的长度。

然后依次遍历数组中的每个元素，对于每一个遍历到的元素A，检查前面的所有子序列，看能不能将A添加到子序列末尾，如果能，这样就形成了一个更长的子序列。在所有能以A为结尾的子序列中找到最长的那个，然后更新dp数组对应的长度。

最后，dp数组中最大值就是所要的结果。

对于这个算法，每次遍历到一个数都要检查前面遍历过的数，时间复杂度是$O(n^2)$，因为要使用到dp数组，空间复杂度也为$O(n)$。

第二个想法

先创建一个数组dp，dp[i]表示长度为i的递增子序列的最后一个数的最小值。

然后依次遍历数组中的每个元素，在遍历到第i个元素时，查看dp数组中下标小于i的元素，如果有数比第i个元素大，就替换这个元素来保证dp[i]表示长度为i的递增子序列的最后一个数的最小值，如果有相等的就什么也不错，如果都比第i个元素小，那么将第i个元素值赋给dp[i]。

最后，dp数组中最后一个有值的元素的下标就是所要的结果。

对于这个算法，每次遍历到一个数都要检查前面遍历过的数，时间复杂度是$O(n^2)$，因为要使用到dp数组，空间复杂度也为$O(n)$。

第三个想法

可以发现在第二个算法中的dp数组应该是一个递增数组。因为每次遍历到第i个数，都只在该数比dp[0..i-1]的数大才将这个数设置给dp[i],所以该数组是递增的。

那么对于这个递增的数组我们可以使用二分查找来提升性能。

这时时间复杂度是$O(nlog(n))$，因为要使用到dp数组，空间复杂度也为$O(n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

import java.util.Arrays;

public class LongestIncreasingSubsequence300 {
	// 算法一
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            int max = dp[i];
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    int tmp = dp[j] + 1;
                    max = max < tmp ? tmp : max;
                }
            }
            dp[i] = max;
            if (dp[i] > res) {
                res = dp[i];
            }
        }
        return res;
    }

    /*
    算法二
    
    dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值  越小
    那么就有更大的可能后面的的数比这个大 从而使整个递增子序列 更长

    dp 数组是递增的  可以用反证法证明
    */
    public int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length + 1]; // dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值
        dp[0] = Integer.MIN_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int j = 0;
            for (; j < res; j++) {
                if (dp[j] == nums[i]) {
                    break;
                } else if (dp[j] > nums[i]) { // 原来的长度为i的递增子序列的最后一个数的可能的最小值 大于 当前遍历到的数
                    dp[j] = nums[i];
                    break;
                }
            }
            if (j == res) { // 当前遍历的数比dp之前的数都大，那么就出现了长度更长的递增子序列
                dp[res++] = nums[i]; 
            }
        }
        return res;
    }

    /*
    算法三
    
    对2的改进
    因为dp是递增的，所以可以将线性遍历改为二分查找
    */
    public int lengthOfLIS3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length + 1]; // dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值
        dp[0] = Integer.MIN_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // Arrays.binarySearch 在 数组的 [fromIndex, toIndex) 不包含toIndex 查找指定的数
            // 找不到 返回  -insertIndex-1
            int p = Arrays.binarySearch(dp, 0, res + 1, nums[i]);
            if (p < 0) {
                p = - (p + 1);
                dp[p] = nums[i];
                res = p > res ? p : res;
            }
        }
        return res;
    }
}

Test

LeetCode测试通过。